package algorithm.dynamicProgramming.p300;

class Solution_v1 {
    public int lengthOfLIS(int[] nums) {
        return lengthOfLIS(nums, 0);
    }

    // 在[index...nums.length]范围内寻找最长上升子序列
    private int lengthOfLIS(int[] nums, int index) {
        if (index == nums.length) {
            return 1;
        }

        int lisLength = 0;
        for (int i = index; i < nums.length; i++) {
            lisLength += Math.max(lisLength, lengthOfLIS(nums, index));
        }

        return lisLength;
    }

    public static void main(String[] args) {
        System.out.println(new Solution_v1().lengthOfLIS(new int[]{1, 3, 2, 4, 3, 2, 5}));
    }
}